//象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
//
// 象棋骑士可能的移动方式如下图所示:
//
//
//
// 我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
//
//
//
// 给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
//
// 你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
//
// 因为答案可能很大，所以输出答案模 10⁹ + 7.
//
//
//
//
//
//
// 示例 1：
//
//
//输入：n = 1
//输出：10
//解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。
//
//
// 示例 2：
//
//
//输入：n = 2
//输出：20
//解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72,
//76, 81, 83, 92, 94]
//
//
// 示例 3：
//
//
//输入：n = 3131
//输出：136006598
//解释：注意取模
//
//
//
//
// 提示：
//
//
// 1 <= n <= 5000
//
//
// Related Topics 动态规划 👍 155 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * @author ldltd
 * @date 2024-12-10 09:11:56
 * @description 935.骑士拨号器

 */

public class KnightDialer {
    public static void main(String[] args) {
    //测试代码
    KnightDialer fun = new KnightDialer();
    Solution solution= fun.new Solution();
    solution.knightDialer(1);

    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    Map<Integer, List<Integer>> map;
    long [][] ar;
    int mod= (int) ((1e9)+7);
    public int knightDialer1(int n) {
        map=Map.of(0,List.of(4,6),
                1,List.of(6,8),
                2,List.of(7,9),
                3,List.of(4,8),
                4,List.of(0,3,9),
                5,List.of(),
                6,List.of(0,1,7),
                7,List.of(2,6),
                8,List.of(1,3),
                9,List.of(2,4));
        //表示从数字i开始，j步能产生多少个组合
        ar=new long[10][5000];
        Arrays.setAll(ar,e->{
            long[] ints = new long[5000];
            Arrays.fill(ints,-1);
            return ints;
        });
        long res=0;
        for (int i = 0; i <=9; i++) {
            long dfs = dfs(i, n-1)%mod;
            res+=  (dfs);
        }
        return (int) (res%mod);

    }
    private long dfs(int i,int n){
        if(n==0) return 1;
        if(ar[i][n]!=-1) return ar[i][n];
        long t=0;
        for (int ne : map.get(i)) {
            t = (t + dfs(ne, n - 1)) % mod;
        }
        ar[i][n] = t;
        return ar[i][n];
    }
    static final int MOD = 1000000007;

    public int knightDialer(int n) {
        int[][] moves = {
                {4, 6},
                {6, 8},
                {7, 9},
                {4, 8},
                {3, 9, 0},
                {},
                {1, 7, 0},
                {2, 6},
                {1, 3},
                {2, 4}
        };
        //d n x， 表示从x开始执行n次后得到的数量
        //这里只有两个0，1，因为只需要最后n的位置，相当于一个滚动数组。计数从1开始，即跳一步，
        int[][] d = new int[2][10];
        Arrays.fill(d[1], 1);
        for (int i = 2; i <= n; i++) {
            //x的取值只有0和1
            int x = i & 1;
            for (int j = 0; j < 10; j++) {
                d[x][j] = 0;
                for (int k : moves[j]) {
                    //d[x^1]  1^1= 0 0^1=1，这里相当于动态规划取上一步，因为起始都是1 ，所以能滚动起来
                    d[x][j] = (d[x][j] + d[x ^ 1][k]) % MOD;
                }
            }
        }
        int res = 0;
        //最后n对应0 1的哪一个不知道，%一下就知道了，然后依次计算0~9的和
        for (int x : d[n % 2]) {
            res = (res + x) % MOD;
        }
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
